Non-bipartite k-common graphs

Abstract: For a given integer $k\ge2$, a graph H is said to be "k-common" if the number of monochromatic copies of H in a k-coloring of the edges of an n-vertex complete graph is asymptotically minimized by a random coloring. Note that the case $k=2$ coincides with the notion of common graphs introduced in 1960s.

We construct the first examples of non-bipartite k-common graphs for $k\ge3$, which resolves a problem of Jagger, Stovícek and Thomason from 1996.

This is a joint work with Dan Kral, Jon Noel, Sergey Norin and Fan Wei.

combinatorics

Audience: researchers in the topic

Comments: password 121323

---

SCMS Combinatorics Seminar

Series comments: Check scmscomb.github.io/ for more information

---